1. Field of the Invention
The present invention relates to a method for coding data and an apparatus for implementing the method. More particularly, the present invention relates to a method for selecting a polynomial used as a base for generating a CRC (Cyclic Redundancy Check) code for detecting an error generated in a transmission line as an error of digital data obtained as a result of coding in a process of recording the digital data onto a magnetic-tape apparatus or an optical-disk apparatus or reproducing the digital data from such an apparatus or in a process to transmit the digital data by making use of a radio transmission system or another system as well as relates to a CRC code used for a CRC coding process making use of the selected polynomial and a CRC coding circuit for carrying out the CRC coding process.
2. Description of the Related Art
In a process to transmit information (or data) through a transmission line used in information-recording apparatus or communication apparatus, an error may be generated in the transmitted information in some cases.
As a method for producing a result of determination as to whether or not transmitted information includes an error, a technology referred to as the CRC (Cyclic Redundancy Check) is widely adopted.
In order to implement the CRC method, it is necessary to carry out a CRC coding process on information to be transmitted prior to transmission. The CRC coding process is explained by referring to FIG. 1 as follows.
FIG. 1 is a diagram showing an information-transmitting apparatus 1 and an information-receiving apparatus 3, which are connected to each other by a transmission line 2. In a CRC process carried out by the information-transmitting apparatus 1, CRC parity bits are added to each information word (or data) to generate CRC code bits, which are then subjected to an error-correction coding process based on typically the Reed-Solomon code. In an error-correction decoding process carried out by the information-receiving apparatus 3, on the other hand, an error included in bits obtained as a result of the error-correction coding process based on typically the Reed-Solomon code is detected and corrected.
To put it in detail, in the information-transmitting apparatus 1, a plurality of information words (data) to be transmitted are supplied to a CRC coder 11 consecutively as an input information string of successive objects of a CRC coding process to be carried out by the CRC coder 11. Details of the CRC coder 11 will be described later by referring to FIG. 2. The information words completing the CRC coding process are supplied to an error correction coder 12 for carrying out an error-correction coding process based on typically the Reed-Solomon code. The information words completing the error-correction coding process are supplied to a transmission line coder 13 for carrying out transmission-line coding process according to the transmission line 2. The information words completing the transmission-line coding process are supplied to the transmission line 2.
The information output by the information-transmitting apparatus 1 is transmitted to a code detector 31 employed in the information-receiving apparatus 3 through the transmission line 2. In the information-receiving apparatus 3, the code detector 31 detects the information and supplies the detected information to a transmission line decoder 32 for carrying out a transmission-line decoding process on the detected information as a counterpart process of the transmission-line coding process carried out by the transmission line coder 13. The transmission line decoder 32 supplies an information string obtained as a result of the transmission-line decoding process to an error correction coder 33 for carrying out an error-correction decoding process based on typically the Reed-Solomon code as a counterpart process of the error-correction coding process carried out by the error correction coder 12. The error correction coder 33 supplies information obtained as a result of the error-correction decoding process to a CRC detector 34 for carrying out a CRC process on the information as a counterpart process of the CRC coding process carried out by the CRC coder 11. The CRC detector 34 carries out the CRC process in order to produce a result of determination as to whether or not the error-correction decoding process has been performed correctly by the error correction coder 33 on the information string output by the transmission line decoder 32 (that is, whether or not the information string still includes an error). The CRC detector 34 outputs the result of the determination as a matching signal. Details of the CRC detector 34 will be explained later by referring to FIG. 5.
The matching signal output by the CRC detector 34 is typically used in a controller employed in a drive of an information-recording apparatus serving as the information-receiving apparatus 3 for improving reliability. The controller makes use of the matching signal to produce a result of determination as to whether or not a request for a retransmission is to be issued to the information-transmitting apparatus 1.
The CRC code is also used as partial information by a host processor of the code detector 31, used as header information and used in a transmitted packet in packet transmission. In addition, the CRC code can also be used as a disappearance flag in an error correction process.
Principle of Error Detection Using CRC Codes
The principle of error detection using CRC codes is explained as follows. An information word, which is digital data of k bits, is provided with r parity bits to form a code word of n (=k+r) bits. In order to derive the concept of a generator polynomial generator G(x) to be explained more below, an (k−1)th-order information polynomial M(x) for expressing the information word in a polynomial expression format is multiplied by xr. For example, in the case of a binary information word of ‘1010101’, which is a binary information word of k (=7) bits, the 6th-order information polynomial M(x) is x6+x4+x2+1.
As described above, the information polynomial M(x) is multiplied by xr to give an expression M(x)·xr, which can be expressed by Eq. (1) given below. In Eq. (1), notation G(x) denotes the aforementioned rth-order generator polynomial, notation Q(x) denotes a quotient polynomial and notation R(x) denotes a (r−1)th-order remainder polynomial. If the expression M(x)·xr is divided by the generator polynomial G(x), the quotient polynomial Q(x) and the remainder polynomial R(x) are resulted in. Eq. (2) is an equation obtained by rearranging Eq. (1) as an equation expressing the product Q(x)·G(x), which is equal to the difference M(x)·xr−R(x). In Eq. (2), notation W(x) denotes an (n−1)th-order transmitted code polynomial expressing the product Q(x)·G(x), which is equal to the difference M(x)·xr−R(x).
[Equation 1]M(x)·xr=Q(x)·G(x)+R(x)  (1)[Equation 2]W(x)=M(x)·xr−R(x)  (2)
Since Eq. (2) obtained as a result of rearranging Eq. (1) indicates that the polynomial W(x) is equal to the product Q(x)·G(x), the transmitted code polynomial W(x) can be divided by the generator polynomial G(x) without leaving a remainder.
From a standpoint based on the above equations, let us assume for example that the information-transmitting apparatus 1 shown in FIG. 1 transmits the transmitted code polynomial W(x) to the information-receiving apparatus 3 through the transmission line 2 and the information-receiving apparatus 3 receives the transmitted code polynomial W(x) as a received code polynomial Y(x). In this case, the CRC detector 34 employed in the information-receiving apparatus 3 examines the received code polynomial Y(x) in order to produce a result of determination as to whether or not the received code polynomial Y(x) can be divided by the generator polynomial G(x) without leaving a remainder.
If the result of the determination indicates that the received code polynomial Y(x) can be divided by the generator polynomial G(x) without leaving a remainder, the received code polynomial Y(x) is determined to be a polynomial matching the transmitted code polynomial W(x). Thus, it is possible to infer that no error has been generated in the information word transmitted through the transmission line 2. If the result of the determination indicates that the received code polynomial Y(x) may not be divided by the generator polynomial G(x) without leaving a remainder, on the other hand, the received code polynomial Y(x) is determined to be a polynomial other than the transmitted code polynomial W(x). Thus, it is possible to determine (or infer) that an error has been generated in the information word transmitted through the transmission line 2.
Since the CRC code is a cyclic code, for a given generator polynomial G(x), the configuration of a circuit for generating the CRC code can be implemented with ease as a configuration employing shift registers and exclusive-or gates. In the case of the information communication system shown in FIG. 1, for example, the circuit for generating the CRC code is the CRC coder 11 employed in the information-transmitting apparatus 1.
Typical CRC Generator
A generator polynomial G(x) widely used in the CRC processing is G(x)=x16+x12+x5+1 or G(x)=x16+x15+x2+1. The former generator polynomial G(x) is a generator polynomial based on the CRC-CCITT standard for the 16-bit CRC (or the CRC with a parity-bit count of 16). On the other hand, the latter generator polynomial G(x) is a generator polynomial based on the CRC-ANSI standard.
Let us assume that r representing the number of parity bits and also representing the order of the generator polynomial G(x) is 3 and assume the rth (3rd)-order generator polynomial G(x)=x3+x+1. In this case, a typical configuration of the CRC coder 11 employed in the information-transmitting apparatus 1 as shown in FIG. 1 is shown in FIG. 2. The CRC coder 11 also referred to as a CRC coding circuit is explained by referring to FIG. 2 as follows.
FIG. 2 is a diagram showing a typical configuration of the CRC coder 11 for generating a transmitted code polynomial W(x) from an information polynomial M(x). As shown in the figure, the CRC coder 11 employs a CRC parity bit generator 110, a first selector 111, a second selector 112 and a bit count counter 113.
The CRC parity bit generator 110 is a unit for generating r parity bits for a string of k information bits and outputting the parity bits to the first selector 111. A method adopted by the CRC parity bit generator 110 as a method for generating the r parity bits will be explained later by referring to FIGS. 3 and 4.
The second selector 112 has a 0 input terminal for receiving the string of k information bits and a 1 input terminal for receiving a string of r parity bits originally generated by the CRC parity bit generator 110 from the first selector 111. While the string of k information bits is being supplied to the 0 input terminal as evidenced by a state control signal S1 generated by the bit count counter 113, the second selector 112 outputs the input string of k information bits as it is to the error correction coder 12. As all the string of k information bits has been output from the second selector 112 to the error correction coder 12 also as evidenced by a change of the state control signal S1, the second selector 112 outputs the string of r parity bits received from the first selector 111 through the 1 input terminal to the error correction coder 12. As described above, the second selector 112 employed in the CRC coder 11 outputs the string of k information bits and the string of r parity bits received from the first selector 111 as a string immediately following the string of k information bits to the error correction coder 12. As described above, the first selector 111 receives the string of r parity bits directly from the CRC parity bit generator 110. That is to say, the second selector 112 outputs a string of (k+r) bits including the string of k information bits and the string of r parity bits to the error correction coder 12.
Next, the CRC parity bit generator 110 and the first selector 111 are described as follows. FIG. 3 is a diagram showing a typical circuit of the CRC parity bit generator 110 designed on the assumption that the generator polynomial G(x) is expressed by the equation G(x)=x3+x+1. As shown in the figure, the CRC parity bit generator 110 has a circuit configuration employing a first shift register R00, a first EXOR (exclusive or) gate EXOR1, a second shift register R01, a third shift register R02 and a second exclusive-or gate EXOR2, which are connected to each other to form a closed loop. In the circuit configuration, the output of the second exclusive-or gate EXOR2 is supplied to one of the input terminals of the first exclusive-or gate EXOR1.
On the other hand, FIG. 4 is a diagram showing a typical circuit of the CRC parity bit generator 110 designed on the assumption that the generator polynomial G(x) is expressed by the equation G(x)=x4+x3+x2+x+1. As shown in the figure, the CRC parity bit generator 110 has a circuit configuration employing a first shift register R00, a first EXOR(exclusive or) circuit EXOR1, a second shift register R01, a second exclusive-or gate EXOR2, a third shift register R02, a third exclusive-or gate EXOR3, a fourth shift register R03 and a fourth exclusive-or gate EXOR4, which are connected to each other to form a closed loop. In the circuit configuration, the output of the fourth exclusive-or gate EXOR4 is supplied to one of the input terminals employed by each of the first exclusive-or gate EXOR1, the second exclusive-or gate EXOR2 and the third exclusive-or gate EXOR3.
As shown in FIGS. 3 and 4, the CRC parity bit generator 110 is designed on the basis of the generator polynomial G(x). In other words, as is understood by referring to FIGS. 3 and 4, for a given G(x), the CRC parity bit generator 110 is configured as a closed loop of shift registers and exclusive-or gates wherein the output of the exclusive-or gate provided at the last stage is supplied to one of the input terminals employed by each of the exclusive-or gates provided at the preceding stages. In the case of the CRC parity bit generator 110 shown in FIG. 3, the second exclusive-or gate EXOR2 is the exclusive-or gate provided at the last stage whereas the first exclusive-or gate EXOR1 is the exclusive-or gate provided at the preceding stage. In the case of the CRC parity bit generator 110 shown in FIG. 4, on the other hand, the fourth exclusive-or gate EXOR4 is the exclusive-or gate provided at the last stage whereas the first exclusive-or gate EXOR1, the second exclusive-or gate EXOR2 and the third exclusive-or gate EXOR3 are the exclusive-or gates provided at the preceding stages.
Next, the operation of the CRC parity bit generator 110 shown in FIG. 3 is described. Since the operation of the CRC parity bit generator 110 shown in FIG. 4 is basically the same as the operation of the CRC parity bit generator 110 shown in FIG. 3, description of the operation of the CRC parity bit generator 110 shown in FIG. 4 is omitted.
In the CRC parity bit generator 110 shown in FIG. 3, an information bit string expressed by the information polynomial M(x) is supplied to the second exclusive-or gate EXOR2 provided on the high-order side of the third shift register R02 at a rate of a bit per time unit. For example, a bit of the information bit string is supplied to the second exclusive-or gate EXOR2 for every clock pulse driving the shift registers R00 to R02. The information bit string is supplied to the second exclusive-or gate EXOR2 sequentially one bit after another, starting with the highest-order bit. Thus, a bit string expressed by a polynomial M(x)·xr, which is a product obtained as a result of multiplying the information polynomial M(x) by xr in advance, is generated in the CRC parity bit generator 110.
The initial values of the first to third shift registers R00, R01 and R02 are each a zero. At a point of time the operation to supply the 0th-order bit of the information bit string to the CRC parity bit generator 110 is completed, the first to third shift registers R00, R01 and R02 contain the coefficients of the terms composing the remainder polynomial R(x). Let us assume that the remainder polynomial R(x) is expressed as a·x2+b·x+c. In this case, the first to third shift registers R02, R01 and R00 contain the values of a, b and c respectively.
Thus, at a point of time the operation to supply the 0th-order bit of the information bit string to the CRC parity bit generator 110 is completed, an enable signal E0 generated by a control circuit not shown in FIG. 2 is put in a disabled (inactive) state to hold the coefficients of the terms composing the remainder polynomial R(x) in the first to third shift registers R00, R01 and R02 and output the coefficients to the first selector 111 as parity bits R00out, R01out and R02out respectively.
As shown in FIG. 2, the first selector 111 has three input terminals 00, 01 and 10 receiving the aforementioned parity bits R00out, R01out and R02out respectively output by the shift registers R00, R01 and R02 respectively employed in the CRC parity bit generator 110 having the circuit configuration shown in FIG. 3. The first selector 111 selects the parity bits R00out, R01out and R02out, which have been received at the input terminals 00, 01 and 10 respectively from the shift registers R00, R01 and R02 respectively, sequentially one bit after another in accordance with a first select signal S0 generated by a control circuit not shown in FIG. 2, and sequentially outputs the selected parity bit to the 1 input terminal of the second selector 112.
As described earlier, while the string of k information bits is being supplied to the 0 input terminal of the second selector 112 as evidenced by a second select signal S1 (or the state control signal S1 mentioned before) generated by the bit count counter 113, the second selector 112 outputs the input string of k information bits as it is to the error correction coder 12. In other words, during a period indicated by the 3-bit contents of the bit count counter 113 controlled by a control circuit not shown in FIG. 2 as a period for inputting the string of k information bits at the 0 input terminal, the second selector 112 selects the input string of k information bits and outputs the input string of k information bits as it is to the error correction coder 12. On the other hand, with a timing indicated by the second select signal S1 as a timing of completions of an operation to supply the input string of k information bits to the CRC parity bit generator 110 and an operation to generate all the r parity bits for the input string of k information bits in the CRC parity bit generator 110, the second selector 112 selects the string of r parity bits received at the 1 input terminal from the first selector 111 and outputs the selected string of r parity bits as it is to the error correction coder 12. As described above, the r parity bits are bits generated by the CRC parity bit generator 110 for the input string of k information bits.
As is obvious from the above description, a string of code bits output by the second selector 112 employed in the CRC coder 11 shown in FIG. 2 to the error correction coder 12 includes the input string of k information bits and the string of r parity bits following the string of information bits. Thus, the string of code bits has a length of n (=k+r) bits.
The process carried out by the CRC coder 11 employed in the information-transmitting apparatus 1 shown in FIG. 1 to add a string of parity bits to a string of information bits as described above is referred to as a CRC coding process. A string of code bits obtained as a result of the CRC coding process is supplied to the error correction coder 12 for carrying out an error-correction coding process based on typically the Reed-Solomon code on the string of code bits. Information obtained as a result of the error-correction coding process is supplied to the transmission line coder 13 for carrying out a transmission-line coding process according to the transmission line 2 on the information and outputting a signal obtained as a result of the transmission-line coding process to the transmission line 2.
The signal is transmitted to the information-receiving apparatus 3 through the transmission line 2. The code detector 31 employed in the information-receiving apparatus 3 receives the signal and detects information from the signal. The code detector 31 then supplies the detected information to the transmission line decoder 32 for carrying out a transmission-line decoding process on the information and outputting an information string obtained as a result of the transmission-line decoding process to the error correction coder 33 for carrying out an error correction process on the information string. Information obtained as a result of the error correction process is supplied to the CRC detector 34 for producing a result of determination as to whether or not the information obtained as a result of the error correction process still includes an error.
FIG. 5 is a diagram showing a typical configuration of the CRC detector 34 for producing a result of determination as to whether or not the received code polynomial Y(x) includes an error. As shown in the figure, the CRC detector 34 employs a parity inspector 341 and a comparator 342.
As described before, the CRC detector 34 is a unit for producing a result of determination as to whether or not the received code polynomial Y(x) can be divided by the generator polynomial G(x) without leaving a remainder. If the result of the determination indicates that the received code polynomial Y(x) can be divided by the generator polynomial G(x) without leaving a remainder, the received code polynomial Y(x) is determined to be a polynomial matching the transmitted code polynomial W(x), that is, no error is determined to have been generated in the transmission of the information word through the transmission line 2. If the result of the determination indicates that the received code polynomial Y(x) may not be divided by the generator polynomial G(x) without leaving a remainder, on the other hand, the received code polynomial Y(x) is determined to be a polynomial not matching the transmitted code polynomial W(x), that is, an error is determined to have been generated in the transmission of the information word through the transmission line 2.
To put it in detail, the parity inspector 341 is a circuit for dividing the received code polynomial Y(x) by the generator polynomial G(x) whereas the comparator 342 is a circuit for producing a result of determination as to whether or not a remainder is left as a result of dividing the received code polynomial Y(x) by the generator polynomial G(x).
FIG. 6 is a diagram showing a typical configuration of the parity inspector 341.
In the system shown in FIG. 1, the CRC detector 34 is the counterpart unit of the CRC detector 34. Thus, the parity inspector 341 shown in FIG. 6 as a circuit employed in the CRC detector 34 is the counterpart circuit of the CRC parity bit generator 110 shown in FIG. 3 as a circuit employed in the CRC coder 11. Therefore, if the circuit shown in FIG. 4 is used as the CRC parity bit generator 110, the parity inspector 341 is designed as the counterpart circuit of the CRC parity bit generator 110 shown in FIG. 4. The following description explains a parity inspector 341 designed as the counterpart circuit of the CRC parity bit generator 110 shown in FIG. 3.
The parity inspector 341 shown in FIG. 6 has a circuit configuration employing a first exclusive-or gate EXOR11, a first shift register R10, a second exclusive-or gate EXOR12, a second shift register R11 and a third shift register R12, which are connected to each other to form a closed loop. In the circuit configuration, the output of the third shift register R12 is supplied to one of the input terminals employed in each of the first and second exclusive-or gates EXOR11 and EXOR12.
In the parity inspector 341 shown in FIG. 6, a received information bit string expressed by the received code polynomial Y(x) is supplied to the first exclusive-or gate EXOR11 provided on the right side of the first shift register R10 at a rate of a bit per time unit. For example, a bit of the received information bit string is supplied to the first exclusive-or gate EXOR11 for every clock pulse driving the shift registers R10 to R12. The information bit string is supplied to the first exclusive-or gate EXOR11 sequentially one bit after another, starting with the highest-order bit.
At a point of time the operation to supply the 0th-order bit of the received information bit string to the parity inspector 341 is completed, the coefficients of the terms composing the remainder polynomial R(x) are held in the first to third shift registers R10, R11 and R12 and the coefficients are output to the comparator 342 as coefficients R10out, R11out and R12out respectively. Let us assume that the remainder polynomial R(x) is expressed as a·x2+b·x+c. In this case, the first to third shift registers R12, R11 and R10 contain the values of a, b and c respectively. The initial values of the first to third shift registers R10, R11 and R12 are each a zero.
As shown in FIG. 5, the parity inspector 341 outputs coefficients generated by the first to third shift registers R10, R11 and R12 employed in the parity inspector 341 as shown in FIG. 6 as the coefficients R10out, R11out and R12out of the remainder polynomial R(x) to the comparator 342.
The comparator 342 examines (or checks) the coefficients R10out, R11out and R12out in order to produce a result of determination as to whether or not all the coefficients R10out, R11out and R12out are zeros, that is, whether or not the remainder polynomial R(x) is a zero. The comparator 342 generates a 1-bit matching signal revealing the result of the determination. That is to say, if the result of the determination indicates that all the coefficients R10out, R11out and R12out are zeros, the received code polynomial Y(x) is determined to be a polynomial matching the transmitted code polynomial W(x) and no error is determined to have been generated in the transmission of the information word through the transmission line 2. In this case, the comparator 342 sets the generated 1-bit matching signal typically at the logic value of 1. If the result of the determination indicates that any of the coefficients R10out, R11out and R12out is not a zero, the received code polynomial Y(x) is determined to be a polynomial not matching the transmitted code polynomial W(x), that is, an error is determined to have been generated in the transmission of the information word through the transmission line 2. In this case, the comparator 342 sets the generated 1-bit matching signal typically at the logic value of 0.
In general, the CRC error detection performance of detecting an error in a code is evaluated in terms of random-error detection performance and burst-error detection performance as well as a code undetected-error probability Pud. The random-error detection performance, the burst-error detection performance and the undetected-error probability Pud are determined by the generator polynomial G(x) and the code length n.
The aforementioned undetected-error probability Pud of a code transmitted through a transmission line is a probability that a received word of the code undesirably changes to a code word other than the transmitted word of the code due to an error generated on the transmission line. The code word other than the transmitted word is a code word including information bits other than transmitted information bits and additional CRC parity bits computed for the other information bits. Since the received word of the code undesirably has changed to another code word, a CRC process carried out on the other code word will result in a division remainder of 0. That is to say, there is a case in which the received code word is determined to include no error in spite of the fact that the received code word includes an error.
Let us assume for example that, in equations given below, notation A denotes a weight distribution, notation B denotes a weight distribution of a dual code and notation εdenotes a state-transition probability representing a probability of a channel bit error in a binary symmetric channel. The weight distributions A and B as well as the channel bit error probability εcan be found from the order r representing the number of parity bits, the code length n and the generator polynomial G(x). In this case, as disclosed in J. K. Wolf, R. D. Blakeney, “An exact evaluation of the probability of an undetected error for certain shortened binary CRC codes,” Military Communications Conference, 1988, MILCOM 88, Conference record. ‘21st Century Military Communications—What's Possible?’. 1988 IEEE vol. 1, pp. 287 to 292, Oct. 1, 1988 (hereinafter referred to as Non-Patent Document 1), the code undetected-error probability Pud can be found from the following equations:
                    [                  Equation          ⁢                                          ⁢          3                ]                                                                      P          ud                =                              ∑                          i              =              1                        n                    ⁢                                    A              i                        ⁢                                                            ɛ                  i                                ⁡                                  (                                      1                    -                    ɛ                                    )                                                            n                -                i                                                                        (        3        )                                [                  Equation          ⁢                                          ⁢          4                ]                                                                      P          ud                =                                            2                              -                r                                      ⁢                                          ∑                                  i                  =                  0                                n                            ⁢                                                                    B                    i                                    ⁡                                      (                                          1                      -                                              2                        ⁢                        ɛ                                                              )                                                  i                                              -                                    (                              1                -                ɛ                            )                        n                                              (        4        )            
The random-error detection performance of the CRC error detection performance is a capability of detecting all of (dmin−1) or fewer random errors where notation dmin denotes the minimum Hamming distance between codes. However, the CRC error detection performance is also capable of detecting an error other than random errors.
The burst-error detection performance of the CRC error detection performance is a capability of detecting all of r or fewer successive burst errors where notation r denotes the order of the generator polynomial G(x) or the number of parity bits. In many cases, however, the CRC error detection performance is also capable of detecting more successive burst errors than r representing the order of the generator polynomial G(x) or representing the number of parity bits.
T. Baicheva, S. Dodunekov, P. Kazakov, “Undetected error probability performance of cyclic redundancy-check codes of 16-bit redundancy,” IEEE Proc.—Commun., vol. 147. no. 5, pp. 253 to 256, October 2000 (hereinafter referred to as Non-Patent Document 2), P. Kazakov, “Fast Calculation of the Number of Minimum-Weight Words of CRC Codes,” IEEE Trans. Inform. Theory, vol. 47, no. 3, pp. 1190 to 1195, March 2001 (hereinafter referred to as Non-Patent Document 3), P. Koopman, “Cyclic Redundancy Code (CRC) Polynomial Selection for Embedded Networks,” The International Conference on Dependable System and Networks, DSN-2004 (hereinafter referred to as Non-Patent Document 4), G. Castagnoli, J. Ganz, P. Graber, “Optimum Cyclic Redundancy-Check Codes with 16-Bit Redundancy,” IEEE Trans. Commun., vol. 38, no. 1, pp. 111 to 114, January 1990 (hereinafter referred to as Non-Patent Document 5), G. Funk, “Determination of Best Shortened Codes,” IEEE Trans. Commun., vol. 44, no. 1, pp. 1 to 6, January 1996 (hereinafter referred to as Non-Patent Document 6), D. Chun, J. K. Wolf, “Special Hardware for Computing the Probability of Undetected Error for Certain CRC Codes and Test Results,” IEEE Trans. Commun., vol. 42, no. 10, pp. 2769 to 2772, October 1994 (hereinafter referred to as Non-Patent Document 7), and G. Castagnoli, S. Brauer, M. Herrmann, “Optimum of Cyclic Redundancy-Check Codes with 24 and 32 Parity Bits,” IEEE Trans. Commun., vol. 41, no. 6, pp. 883 to 892, June 1993 (hereinafter referred to as Non-Patent Document 8) are a variety of reports each describing a generator polynomial for minimizing the code undetected-error probability Pud. A variety of such generator polynomials are each proposed as a polynomial designed in accordance with a given order r of the polynomial (or in accordance with the parity-bit count r representing the number of parity bits) and a given length of the code.
In particular, Non-Patent Documents 2 and 3 are each a report proposing generator polynomials each used for minimizing the code undetected-error probability Pud for different code lengths n in the case of 16-bit CRC processing or CRC processing based on a parity-bit count of 16.
Non-Patent Documents 5 and 8 each confirm a property indicating that, as the code length n changes, the code undetected-error probability Pud extremely increases when the code length is raised from a value smaller than a specific value to a value greater than the specific value on both sides of which the code minimum Hamming distance dmin has different values.
FIG. 7 is a diagram showing a graph representing a typical characteristic of the minimum (lower limit) undetected-error probability Pud of 8-bit CRC processing or CRC processing based on a parity-bit count of 8. In the diagram of FIG. 7, the horizontal axis represents the code length n expressed in terms of bits whereas the vertical axis represents the code undetected-error probability Pud. The curve shown in the figure is referred to as an n−Pud characteristic.
J. M. Stein, “METHOD FOR SELECTING CYCLIC REDUNDANCY CHECK POLYNOMIALS FOR LINEAR CODED SYSTEMS,” U.S. Pat. No. 6,085,349, Qualcomm Incorporated, Filed Aug. 27, 1997 (hereinafter referred to as Patent Document 1) discloses an invention relating to a method for selecting a CRC generator polynomial. In accordance with the invention disclosed in Patent Document 1, for a given generator-polynomial order r, a generator polynomial is selected on the basis of a distance spectrum computed for all generator polynomials having the order r. This distance spectrum is a table showing the number of code words at their minimum Hamming distances. From this table, generator polynomials having largest minimum Hamming distances are selected and, finally, a generator polynomial minimizing the code undetected-error probability Pud is chosen.